package com.javatest2;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;

/**
 * @program: item_02
 * @description: 描述
 * 今天有
 * N
 * 个面试者需要面试，公司安排了两个面试的城市A和B，
 * 每一个面试者都有到A城市的开销costA和到B城市的开
 * 销costB。公司需要将面试者均分成两拨，使得total
 * cost最小。
 * 说明
 * ✪ N是偶数
 * ✪ 2<=N<=1e5
 * ✪ 答案确保在int范围内
 * ✪ 1<=costA,costB <=1e6
 * 示例
 * 2021/2/8 题目
 * https://share.jiuzhang.com/problem?id=1895 2/2
 * 输入: cost = [[5,4],[3,6],[1,8],[3,9]]
 * 输出: 14
 * 说明: 第一个和第二个人去B城市，剩下的去A城市
 * @author: LL
 * @create: 2021-02-08 13:39
 */
public class Subject15 {
    /**
     * 解法：排序
     * 算法：排序
     * 解题思路
     * 对于每一个人去A城市的距离减去B城市的距离，从小到
     * 大进行排序，前一半的人去A城市，后一半的人去B城市。
     * 复杂度分析
     * 时间复杂度：O(nlogn)
     * 需要进行排序，排序算法时间为nlogn。
     * n/2costA+n/2costB= n/2(costA+CostB)=n/2(CostA+CostA+CostB-CostA)= n*CostA + n/2(CostB-CostA
     * 2021/2/8
     */

    public static int test(final List<List<Integer>> cost) {
        final Comparator<List<Integer>> comparator = new Comparator<List<Integer>>() {
            @Override
            public int compare(final List<Integer> o1, final List<Integer> o2) {
                if (o1.get(1) - o1.get(0) == o2.get(1) - o2.get(0)) {
                    return 0;
                } else if (o1.get(1) - o1.get(0) < o2.get(1) - o2.get(0)) {
                    return -1;
                } else {
                    return 1;
                }
            }
        };

        Collections.sort(cost, comparator);
        int answer = 0;
        final int size = cost.size();
        int j = 0;
        for (int i = 0; i < size; i++) {
            if (2 * j < size) {
                answer += cost.get(i).get(1);
            } else {
                answer += cost.get(i).get(0);
            }
            j++;
        }
        System.out.println(answer);
        return answer;
    }

    public static void main(final String[] args) {
        final List<List<Integer>> operation = new ArrayList<>();
        //[[5,4],[3,6],[1,8],[3,9],[1,10],[7,6]]
        //1,3,7,6,9,1

        final List<Integer> opa = new ArrayList<>();
        opa.add(5);
        opa.add(4);
        operation.add(opa);

        final List<Integer> opa1 = new ArrayList<>();
        opa1.add(3);
        opa1.add(6);
        operation.add(opa1);

        final List<Integer> opa2 = new ArrayList<>();
        opa2.add(1);
        opa2.add(8);
        operation.add(opa2);

        final List<Integer> opa3 = new ArrayList<>();
        opa3.add(3);
        opa3.add(9);
        operation.add(opa3);

        final List<Integer> opa4 = new ArrayList<>();
        opa4.add(1);
        opa4.add(10);
        operation.add(opa4);

        final List<Integer> opa5 = new ArrayList<>();
        opa5.add(7);
        opa5.add(6);
        operation.add(opa5);

        test(operation);
    }

}
